package mashibing.class23;

import java.util.Arrays;

/**
 * 给定一个正数数组arr，
 * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
 * 返回：
 * 最接近的情况下，较小集合的累加和
 */
public class Class23_1_SplitSumClosed {

    public static int splitSumClosed1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = Arrays.stream(arr).sum();
        return process(arr, 0, sum / 2);
    }

    private static int process(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return 0;
        } else {
            int p1 = process(arr, i + 1, rest);
            int p2 = 0;
            if (arr[i] <= rest) {
                p2 = arr[i] + process(arr, i + 1, rest - arr[i]);
            }
            return Math.max(p1, p2);
        }
    }

    public static int splitSumClosed2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = Arrays.stream(arr).sum();
        sum /= 2;
        int dp[][] = new int[arr.length + 1][sum + 1];
        // dp[n][...] = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int rest = 0; rest <= sum; rest++) {
                int p1 = dp[i + 1][rest];
                int p2 = 0;
                if (arr[i] <= rest) {
                    p2 = arr[i] + dp[i + 1][rest - arr[i]];
                }
                dp[i][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][sum];
    }

    public static void main(String[] args) {
        int[] arr = {1, 6, 7, 4, 3, 2};
        System.out.println(splitSumClosed1(arr));   // 11
        System.out.println(splitSumClosed2(arr));   // 11
    }
}
